#include <cmath>
#include <algorithm>

class Solution
{
public:
    Solution() {}
    int twoCitySchedCost(vector<vector<int>> &costs)
    {
        int n = costs.size() / 2;
        sort(costs.begin(), costs.end(), Solution::signedCostDiffComparator);
        // 按照aCost-bCost由大到小排序，前n个去a，后n个去b即可
        int totalCost = 0;
        for (int i = 0; i < n; ++i)
        {
            totalCost += costs[i][0] + costs[i + n][1];
        }
        return totalCost;
    }

private:
    static bool unsigendCostDiffComparator(const vector<int> &left, const vector<int> &right)
    {
        return abs(left[0] - left[1]) < abs(right[0] - right[1]);
    }

    static bool signedCostDiffComparator(const vector<int> &left, const vector<int> &right)
    {
        return (left[0] - left[1]) < (right[0] - right[1]);
    }

    // 一开始的思路：按照差值的绝对值由大到小排序，然后依次派往cost的较低的地区
    // 如果一个地方派满了，剩下的都去往另一个地方
    // 从数学角度来说和题解是一样的
    // 从程序上看，渐进时间复杂度都是O(nlogn)，但是这种方法多了一些不必要的计算
    int sortByAbsDiff(vector<vector<int>> &costs)
    {
        int n = costs.size() / 2;
        sort(costs.rbegin(), costs.rend(), Solution::unsigendCostDiffComparator);
        int numToA = 0;
        int numToB = 0;
        int totalCost = 0;
        for (auto &cost : costs)
        {
            if (numToA == n)
            {
                totalCost += cost[1];
            }
            else if (numToB == n)
            {
                totalCost += cost[0];
            }
            else
            {
                if (cost[0] <= cost[1])
                {
                    totalCost += cost[0];
                    ++numToA;
                }
                else
                {
                    totalCost += cost[1];
                    ++numToB;
                }
            }
        }
        return totalCost;
    }
};